"""
堆排序是一种基于二叉堆数据结构的比较排序算法。
它将要排序的序列构造成一个高度平衡的二叉堆（可以是最大堆或最小堆），
然后逐步将堆顶元素与末尾元素交换，缩小堆范围，并重新调整为新的堆，
直到所有元素都被排序完毕。

### 涉及的概念：

1. **二叉堆**：一种特殊的完全二叉树，其中每个节点的值都大于等于（最大堆）或小于等于（最小堆）其子节点的值。
2. **堆性质**：对于最大堆而言，任何给定节点的键都必须大于或等于其子节点的键；对于最小堆，则相反。
3. **完全二叉树**：除了最后一层外，每一层的节点都是满的，并且最后一层的叶子节点都是靠左排列。
4. **堆调整（Sift Down）**：从树的某个非叶子节点开始，将该节点与其子节点进行比较，如果发现子节点比父节点更大（或更小，取决于堆类型），则交换它们的位置，然后继续比较该节点与其新的子节点，直到不需要再做任何交换为止。
5. **构建初始堆（Build Heap）**：将无序数组构造成满足堆性质的堆结构。

### 为什么使用大根堆（最大堆）排序？

使用大根堆进行排序有几个优点：

- **稳定性**：大根堆可以确保每次都能取出当前未排序部分的最大值，这有助于实现稳定的排序过程。
- **效率**：构建初始堆的时间复杂度为 O(n)，而每次调整堆的时间复杂度为 O(log n)，整个排序过程的时间复杂度为 O(n log n)。
- **空间效率**：堆排序是原地排序算法，除了几个变量之外，不需要额外的空间来存储临时数组等。
- **适应性**：堆排序适用于大数据量的情况，因为它能够有效地处理大量的数据排序。

总的来说，使用大根堆排序可以使我们更容易地提取出数组中的最大值，
从而逐步构建出一个降序排列的数组。如果需要得到升序排列的结果，
可以在每一步提取最大值后，将其放置在正确的位置。
"""
def parent_down(heap, heap_size, parent_index):
    """ 实现父节点下沉 """

    left_child_index = 2 * parent_index + 1  # 左边子节点的下标

    while left_child_index < heap_size:
        # 如果该父节点有右孩子，那就比较两个孩子的大小，求出最大孩子的下标
        largest = (left_child_index + 1) if left_child_index + 1 < heap_size and heap[left_child_index + 1] > heap[left_child_index] else left_child_index

        if heap[parent_index] >= heap[largest]:
            break

        heap[parent_index], heap[largest] = heap[largest], heap[parent_index]

        parent_index = largest
        left_child_index = 2 * parent_index + 1


def heap_sort(my_list):
    """ 堆排序 """
    
    n = len(my_list)  # 堆的长度（大小）

    # 构建一个大根堆：从最后一个非叶子节点开始（从下往上开始）
    # end_parent_index 表示：最后一个非叶子节点的下标
    end_parent_index = (n-2) // 2
    for i in range(end_parent_index, -1, -1):
        parent_down(my_list, n, i)

    # 循环的从大根堆中删除根节点（堆顶），把每次循环的最大值放到列表的后面（升序排序）
    for i in range(n-1, 0, -1):
        # 把堆中第一个值（堆顶，最大值）交换到列表中的后面
        my_list[0], my_list[i] = my_list[i], my_list[0]
        # 堆要开始进行调整
        parent_down(my_list, i, 0)


if __name__ == '__main__':
    my_list = [1, 3, 4, 5, 2, 6, 9, 7]
    heap_sort(my_list)
    print(my_list)
